from tools_algorithm import *


class Solution:
    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
        h, cnt, n = Counter(), 0, len(words)
        for word in words:
            cnt += 1 if len(word) & 1 == 1 else 0
            for w in word:
                h[w] += 1
        a, b = 0, 0
        for k, v in h.items():
            a += v % 2
            b += v // 2
        if a <= cnt:
            return n
        words.sort(key=lambda a: len(a))
        ans = 0
        for word in words:
            s = len(word)
            if s // 2 <= b:
                b -= s // 2
                if s & 1 == 1:
                    if a > 0:
                        a -= 1
                    else:
                        a += 1
                        b -= 1
                ans += 1
        return ans

        # @cache
        # def f(i, a, b):
        #     if i == n:
        #         return 0
        #     s = len(words[i])
        #     ans = f(i + 1, a, b)
        #     if s & 1 == 0 and s // 2 <= b:
        #         ans = max(ans, f(i + 1, a, b - s // 2) + 1)
        #     if s & 1 == 1 and s // 2 <= b and a > 0:
        #         ans = max(ans, f(i + 1, a - 1, b - s // 2) + 1)
        #     if s & 1 == 1 and s // 2 < b:
        #         ans = max(ans, f(i + 1, a + 1, b - s // 2 - 1) + 1)
        #     return ans

        return f(0, a, b)
